#pragma once

// 6.有一个带头结点的单链表L,设计一个算法使其元素递增有序。

// #include "vector"
#include "list"
#include "iostream"
#include "memory"
#include "assert.h"
// #define mallocFor(Type) malloc(sizeof())
// template <

// template <typename ElemType>
// ElemType *mallocListNode();

template <typename ElemType>
struct ListNode
{
	ElemType value;
	// std::shared_ptr<ListNode<ElemType>> next;
	ListNode<ElemType>* next;
	// ListNode() {}

	//辅助检查代码问题
	~ListNode()
	{
		std::cout << "node value " << value << " destroyed\r\n";
	}
	void print2End()
	{
		ListNode<ElemType>* curNode = this;
	loop:
		if (curNode)
		{
			std::cout << curNode->value << ",";
			curNode = curNode->next;
			goto loop;
		}
		// if (curNode->next)
		// {

		// }
		std::cout << std::endl;
		//while()
	}
};

//无头节点链表构造
template <typename ElemType>
void initListByArr(ListNode<ElemType>* head, ElemType arr[], size_t arrLen)
{
	ListNode<ElemType>* curNode = head;
	//value = arr[0];
	// curNode->value = arr[0];
	for (int i = 0; i < arrLen; i++)
	{
		curNode->next = mallocListNode<ElemType>(); //(ListNode<ElemType> *)malloc(sizeof(ListNode<ElemType>)); //std::make_shared<ListNode<ElemType>>();
		curNode = curNode->next;
		curNode->value = arr[i];
	}
}

template <typename ElemType>
ListNode<ElemType>* mallocListNode()
{
	auto ret = (ListNode<ElemType> *)malloc(sizeof(ListNode<ElemType>));
	ret->next = NULL;
	return ret;
	// ret
}

template <typename ElemType>
void ListQuickSort(ElemType arr[], int left, int right)
{
	// auto pivot = left;
	auto pivotValue = arr[left]; //一定要记录值，因为之后下标将无法指向原先的值
	bool onRight = true;
	auto leftBak = left;
	auto rightBak = right;
	while (right != left)
	{
		if (onRight)
		{
			if (arr[right] >= pivotValue)
			{
				right--;
			}
			else
			{
				arr[left] = arr[right];
				left++;
				onRight = false;
			}
		}
		else
		{
			if (arr[left] <= pivotValue)
			{
				left++;
			}
			else
			{
				arr[right] = arr[left];
				right--;
				onRight = true;
			}
		}
	}
	arr[right] = pivotValue;
	if (leftBak < right - 1) //确保范围有效
	{
		ListQuickSort(arr, leftBak, right - 1);
	}
	if (rightBak > right + 1) //确保范围有效
	{
		ListQuickSort(arr, right + 1, rightBak);
	}
}

/**
 * 空间换时间
*/
template <typename ElemType>
void ListSortIncrease_Copy2Arr(ListNode<ElemType>* head)
{
	int size = 0;
	auto cur = head->next;
	while (cur)
	{
		size++;
		cur = cur->next;
	}
	ElemType* arr = (ElemType*)malloc(sizeof(ElemType) * size);
	cur = head->next;
	size = 0;
	while (cur)
	{
		arr[size] = cur->value;
		size++;
		cur = cur->next;
	}
	ListQuickSort(arr, 0, size - 1);
	cur = head->next;
	size = 0;
	while (cur)
	{
		cur->value = arr[size];
		size++;
		cur = cur->next;
	}
}

template <typename ElemType>
void ListSortIncrease(ListNode<ElemType>* head)
{
	auto oldHead = head;
	//auto curPre = head->next;
	//auto curPreBak = head->next;
	//auto newConnect = head;
	//auto old = head->next;

	//关键，head节点用来接新内容了，所以要拷贝头节点
	ListNode<ElemType> oldPre = *head;
	auto oldPrePtr = &oldPre; //head;
	//auto nextBegin = head;
	while (oldPrePtr->next) //如果旧链表里还有有效数据
	{
		auto curPre = oldPrePtr;
		auto minPre = curPre;
		//curPre = curPre->next;
		while (curPre)
		{
			if (curPre->next && curPre->next->value < minPre->next->value)
			{
				minPre = curPre;
			}
			curPre = curPre->next;
		}
		//链接最小节点到head后
		head->next = minPre->next;
		// head变为新链接节点，为之后链接做准备
		head = head->next;
		//如果存在最小节点，则移除
		if (minPre->next)
		{
			minPre->next = minPre->next->next;
		}
		//旧链表节点前移
		// oldPrePtr = oldPrePtr->next;
	}
}

int main()
{
	std::cout << "hello \r\n";
	int arrA[] = {
		7,
		7, 7, 4, 7, 5, 6, 2, 1, 3

	};
	int arrB[] = { -25, -10, 10, 11 };
	int arrC[] = { 2, 9, 17, 30, 41 };

	//ListNode<int> a(arrA, sizeof(arrA) / sizeof(int));
	auto head = mallocListNode<int>(); //std::make_shared<ListNode<int>>(arrA, sizeof(arrA) / sizeof(int));
	initListByArr(head, arrA, sizeof(arrA) / sizeof(int));
	head->next->print2End();
	// delElemX(head->next, 7);

	// printFromEnd(head);
	// deleteMinNode(head);
	//revertListWithHead(head);
	// ListSortIncrease_Copy2Arr(head);
	ListSortIncrease(head);
	if (head->next)
	{
		head->next->print2End();
	}
	else
	{
		std::cout << "del 2 null\r\n";
	}
	//a.print2End();
	// std::vector<int> A =
	////     std::vector<int> B =
	//std::vector<int> A(arrA, arrA + sizeof(arrA) / sizeof(int));
	//// std::vector<int> B(arrB, arrB + sizeof(arrB) / sizeof(int));
	//// std::vector<int> C(arrC, arrC + sizeof(arrC) / sizeof(int));

	//printVec(A);
	//// printVec(B);
	//// printVec(C);
	//quickSortStart(A);
	//printVec(A);
	// std::vector<int> vec1; // vec2, vec3;
	// int arr[100];
	// std::cout << "hello"
	//           << "\r\n";
	// //init data
	// for (int i = 0; i < 100; i++)
	// {
	//     arr[i] = i;
	// }
	// leftMoveArr(arr, 100, 30);

	// // fastFind(vec1, 9);
	// for (int i = 0; i < 100; i++)
	// {
	//     std::cout << arr[i] << ",";
	// }
	// std::cout << "\r\n";
	// for (int i = 0; i < vec2.size(); i++)
	// {
	//     std::cout << vec2[i] << ",";
	// }
	// std::cout << "\r\n";
	// ///////////////////////////////////////////////////
	// combineAB2C(vec1, vec2, vec3);
	// for (int i = 0; i < vec3.size(); i++)
	// {
	//     std::cout << vec3[i] << ",";
	// }
	// std::cout << "\r\n";
	return 0;
}